# 数组中第k个最大元素： https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

import random
class Solution:
    def findKthLargest(self, nums: list, k: int) -> int:
        """
            使用快速排序，当下标出现k时，返回即可，不需要完全排序,
            这里使用的是由大到小排列， k-1 == p
            如果是从小到大排列就该是： p == len(nums) - k
        """

        def Pivotkey(nums, low, high):
            pivot = random.randint(low, high)
            nums[high], nums[pivot] = nums[pivot], nums[high]

            i = j = low
            while j < high:
                if nums[j] > nums[high]:
                    nums[j], nums[i] = nums[i], nums[j]
                    i += 1
                j += 1

            # 交换中间值
            nums[i], nums[high] = nums[high], nums[i]
            return i

        
        def QuickSort(nums, low, high):
            # 注意！！ 不需是 <= ，当low == high时，这个元素可能就是需要的呢？ 所以必须做判断
            if low <= high:
                p = Pivotkey(nums, low, high)
                if k-1 == p:
                    return nums[p]
                elif p < k - 1:
                    return QuickSort(nums, p + 1, high)
                else:
                    return QuickSort(nums, low, p - 1)
        
        return QuickSort(nums, 0, len(nums) - 1) 



# 最小堆解题
import random
class Solution:
    def findKthLargest(self, nums: list, k: int) -> int:
        """
            典型的求TopK的问题！ 使用最小堆解决问题（小根堆），创建K长度的最小堆
            时间复杂度： O(nlog(k))
        """
        def heapAdjust(nums, start, end):
            """ 调整堆 """
            rc = nums[start]
            i = start
            while i * 2 + 1 <= end:
                j = i * 2 + 1
                if j < end and nums[j] > nums[j + 1]: j += 1
                if rc < nums[j]: break
                nums[i] = nums[j]
                i = j
            
            nums[i] = rc
        
        def heapPush(nums, num):
            """ 向堆中添加元素 """
            nums.append(num)
            n = len(nums)
            i = n - 1
            while (i - 1) // 2 >= 0:
                j = (i - 1) // 2
                if nums[j] < num: break
                nums[i] = nums[j]
                i = j
            
            nums[i] = num
        
        # 下面开始，创建 k长度的最小堆
        heap = []
        for num in nums:
            # 当小于k就一直添加元素
            if len(heap) < k:
                heapPush(heap, num)
            # 判断与堆顶的大小关系，大于就压进去
            elif num > heap[0]:
                heap[0] = num
                heapAdjust(heap, 0, k - 1)

        return heap[0]


nums = [1]
k = 1
s = Solution()
rst = s.findKthLargest(nums, k)
print(rst)
